In this paper, LPT (largest processing time) algorithm is considered for scheduling\njobs with similar sizes on three machines. The objective function is to\nminimize the maximum completion time of all machines. The worst case\nperformance ratio of the LPT algorithm is given as a piecewise linear function\nof r if job sizes fall in [1, r]. Our result is better than the existing result. Furthermore,\nthe ratio given here is the best. That means our result cannot be\nimproved any more.
Loading....